package class3;

import common.ListNode;
import common.ListNodeUtils;
import test.TestDemo;

import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 给你一个链表数组，每个链表都已经按升序排列。
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 * 示例 1：
 * <p>
 * 输入：lists = [[1,4,5],[1,3,4],[2,6]]
 * 输出：[1,1,2,3,4,4,5,6]
 * 解释：链表数组如下：
 * [
 * 1->4->5,
 * 1->3->4,
 * 2->6
 * ]
 * 将它们合并到一个有序链表中得到。
 * 1->1->2->3->4->4->5->6
 */
public class Code09_MergeKSortedLists {
    public static void main(String[] args) {
        ListNode node1 = ListNodeUtils.getLinked(new int[]{1, 4, 5});
        ListNode node2 = ListNodeUtils.getLinked(new int[]{1, 3, 4});
        ListNode node3 = ListNodeUtils.getLinked(new int[]{2, 6});
        ListNode[] listNodes = new ListNode[]{node1, node2, node3};
        ListNode listNode = mergeKSortedLists(listNodes);
        ListNodeUtils.print(listNode);

        ListNode listNode1 = mergeKSortedLists2(listNodes);
        ListNodeUtils.print(listNode1);
    }

    public static ListNode mergeKSortedLists(ListNode[] lists) {
        if (lists == null) {
            return null;
        }
        PriorityQueue<ListNode> heap = new PriorityQueue<ListNode>(new ListNodeComparator());
        for (int i = 0; i < lists.length; i++) {
            if (lists[i] != null) {
                heap.add(lists[i]);
            }
        }
        if (heap.isEmpty()) {
            return null;
        }
        // 弹出一个节点，当头
        ListNode head = heap.poll();
        ListNode pre = head;
        if (pre.next != null) {
            heap.add(pre.next);
        }
        while (!heap.isEmpty()) {
            ListNode cur = heap.poll();
            pre.next = cur;
            pre = cur;
            if (cur.next != null) {
                heap.add(cur.next);
            }
        }
        return head;

    }

    public static ListNode mergeKSortedLists2(ListNode[] arr) {
        if (arr == null) {
            return null;
        }
        PriorityQueue<ListNode> heap = new PriorityQueue<>(new ListNodeComparator());
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] != null) {
                heap.add(arr[i]);
            }
        }
        ListNode head = null, pre = null,cur=null;

        while (!heap.isEmpty()) {
            // 从堆中弹出当前最小节点
            cur = heap.poll();
            // 如果合并链表为空，则初始化头节点
            if (head == null) {
                head = cur;
            } else {
                pre.next = cur;
            }
            // 更新pre为当前节点
            pre = cur;
            // 如果当前节点有下一个节点，加入堆中
            if (cur.next != null) {
                heap.add(cur.next);
            }
        }

        return head;
    }
    /**
     * ListNode 比较器
     */
    static class ListNodeComparator implements Comparator<ListNode> {
        @Override
        public int compare(ListNode o1, ListNode o2) {
            return o1.val - o2.val;
        }
    }
}
